Digital filtering is a class of image processing. Rank filtering is one type of digital filtering which is widely used in image processing, for example, for eliminating/reducing noise in an image. It is a technique for performing non-linear smoothing of a single- or multi-dimensional signal consisting of discrete samples.
An output sample is generated by the filter for each such input sample, using a window size and a rank value to specify the characteristics of the filter. The rank filter is a sorting algorithm in which data values (e.g., pixels) within the window are sorted in numerical order. The output value is the nth lowest data value within the window, where n is the rank order of the filter. When n is the median sample, the rank-order filter could be referred to as a median filter. More particularly, a rank filter replaces a data value, corresponding to a predetermined rank, among multiple data values within the window. The data set value corresponding to the center position of the window is replaced. Accordingly, there can only be an odd number of data values in the window since the result of the filter is stored in the location on which the window is centered.
Using two examples, the concept of a rank filter is briefly explained in order to help in understanding a rank filter. FIG. 1 shows a first example of performing a rank filtering in the case of data values within a 3.times.3 window. If the data values (shown at the left of the figure) are arranged starting with the largest number and ending with the smallest number, they become: 15, 12, 11, 10, 7, 6, 5, 5, 2. If a predetermined rank of 5 is selected, the data position corresponding with the center position of the 3.times.3 window (which has a value of 2), is replaced with the value of 7, since 7 is the magnitude corresponding to the 5.sup.th value (i.e., rank of 5) of the nine data values (as shown at the right of the figure). For this particular example, since the value of 7 is a median value of the nine data values, the filter could be referred to as a median filter.
FIG. 2 shows a second example of performing a rank filter in a case of data values within a 5.times.1 window. If the data values (shown at the left of the figure) are arranged starting with the largest number and ending with the smallest number, they become: 11, 10, 7, 6, 5. If a predetermined rank of 3 is selected, the data position corresponding with the center position of the 5.times.1 window (which has a value of 10), is replaced with the value of 7, since 7 is the magnitude corresponding to the 3rd value (i.e., rank of 3) of the five data values. The ranked data values are shown at the right of the figure.
Numerous designs exist in the prior art for both one-dimensional and two-dimensional rank filters. U.S. Pat. No. 5,408,675 is directed to a hardware implementation of a programmable rank order filter using a first-in-first-out approach to track the values and the rank number for each corresponding value. U.S. Pat. No. 5,315,171 determines the rank value by the summation from comparator of the inputs to the feedback value. U.S. Pat. No. 5,113,484 determines the rank element by comparing in order the rank desired with occurrences of each possible value.
While such apparatus may have achieved certain degrees of success in their particular applications, because of the constant sorting of the data value in the window, the processing of an image using this technique can be compute intensive. In addition, memory requirements to perform the filtering may require space for both the original image and the processed image. Further, such filtering may be limited to a particular window size or rank element, or require that the filter be implemented solely in hardware or solely in software.
Accordingly, a need continues to exist for a rank filter which does not consume significant processing time, is not limited to a particular window size or rank element, does not require significant computer memory, and can be implemented in both hardware and software.